This invention relates to a Reed-Solomon encoding device and method and, in particular, to such device and method adapted to error correction of a desired number of blocks not fewer than two.
In data communication, a redundancy signal is generally appended to data (information signal) to be transmitted so that a data error occurring in a transmission path can be detected and corrected at a receiving end. As the redundancy signal to be appended to the information signal, a Reed-Solomon code is widely known.
Examples of a device for carrying out Reed-Solomon encoding are disclosed in Japanese Unexamined Patent Publications (JP-A) Nos. 59-226951 (226951/1984), 60-73752 (73752/1985), and 9-36753 (36753/1997). However, each of these publications discloses no more than a Reed-Solomon encoding device adapted to error correction of a single block or two blocks at most.
In contrast, as a Reed-Solomon encoding circuit adapted to error correction of a desired number of blocks not fewer than two, a circuit using a polynomial division circuit is disclosed in "Essence of Error Correction Encoding Technique" (supervised by Hideki Imai, Japan Industrial Technology Center, 1986), page 30 (hereinafter called a conventional example 1). In addition, a circuit for successively processing input signals in a systolic array structure is disclosed in "A Construction Method for Reed-Solomon Codec Suitable for VLSI Design" (Proceedings of Institute of Electronics, Information, Communication Engineers of Japan, Vol. J71-A, pp. 751-759) (hereinafter called a conventional example 2).
FIG. 1 is a block diagram showing a structure of the Reed-Solomon encoding circuit in the conventional example 1.
The Reed-Solomon encoding circuit of the conventional example 1 comprises a division circuit which is composed of exclusive-OR circuits 531 through 53n, Galois field multiplication circuits 541 through 54n, and D flop-flops 551 through 55n, and which calculates a formula obtained by dividing a polynomial corresponding to an input signal by a generator polynomial. Note that multipliers of the Galois field multiplication circuits 541 through 54n are determined from coefficients of the generator polynomial F(x) represented by Equation (1). EQU F(x)=(x+.alpha.)(x+.alpha..sup.2)(x+.alpha..sup.3) . . . (x+.alpha..sup.m) (1)
In the above-mentioned Reed-Solomon encoding circuit, a selector 52 is responsive to a count value of a counter 51 and selects either the input information signal or an output signal of the D flop--flop 55n as a selector output. Thus, the selector 52 successively outputs the information signal and a Reed-Solomon code as a redundancy code. Herein, by controlling which one is to be outputted from the selector 52 with reference to the count value of the counter 51, it is possible to produce the Reed-Solomon code permitting error correction of a desired number of blocks.
FIG. 2 is a block diagram showing a structure of the Reed-Solomon encoding circuit in the conventional example 2.
As illustrated in the figure, the Reed-Solomon encoding circuit in the convention example 2 comprises a division circuit formed by connecting in cascade a plurality of processing elements PE illustrated in FIG. 3, instead of the division circuit composed of the exclusive-OR circuits 531 through 53n, the Galois field multiplication circuits 541 through 54n, and the D flop-flops 551 through 55n illustrated in FIG. 1.
However, in each of the circuits in the conventional examples 1 and 2, the information signal is supplied one byte by one byte. Every time when the information signal is supplied, orders or degrees are lowered by one at a time. After completion of input of the information signal, redundancy signals corresponding to respective terms of a remainder polynomial as a result of calculation are successively outputted. Therefore, it takes a long time before completion of the Reed-Solomon encoding.